/**
 DP
 * @param {number[]} prices
 * @return {number}
 */
export var maxProfit = function (prices) {
  // 记录第i天取得的最大利润， 0为手上没有股票， 1为手上有股票
  const dp = new Array(prices.length).fill(0).map(() => new Array(2).fill(0))
  dp[0][0] = 0
  dp[0][1] = -prices[0]

  for (let i = 1; i < prices.length; i++) {
    // 第i天没有股票，可能是昨天没持股票，或者是昨天持有，但今天卖出了
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    // 第i天有股票，可能是昨天没有股标，但今天买入，又或者昨天已持有
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
  }
  return dp[prices.length - 1][0]
}

/**
 贪心
 * @param {number[]} prices
 * @return {number}
 */
export var maxProfit2 = function (prices) {
  let ans = 0
  let n = prices.length
  for (let i = 1; i < n; ++i) {
    ans += Math.max(0, prices[i] - prices[i - 1])
  }
  return ans
}
